package day24;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * 题目：迷宫问题
 * 题目链接：https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?tpId=37&&tqId=21266&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
 * 广度优先搜索(BFS)
 */

class Node {
    int x;
    int y;
    public Node(int x,int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main1 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String leng;
        while ((leng = reader.readLine()) != null) {
            String[] strings = leng.split(" ");
            int row = Integer.parseInt(strings[0]);
            int col = Integer.parseInt(strings[1]);
            int[][] mat = new int[row][col];
            for (int i = 0; i < row; i++) {
                leng = reader.readLine();
                strings = leng.split(" ");
                for (int j = 0; j < col; j++) {
                    mat[i][j] = Integer.parseInt(strings[j]);
                }
            }
            ArrayList<Node> path = new ArrayList<>();
            ArrayList<Node> minPath = new ArrayList<>();
            int[][] book = new int[row][col];
            getMinPath(mat,row,col,0,0,book,path,minPath);
            for (Node node:minPath) {
                System.out.println("("+node.x+","+node.y+")");
            }
        }
    }

    //mat表示迷宫矩阵 ，row col
    //x，y表示当前位置
    //book: 标记矩阵，标记当前位置是否走过
    //path: 保存当前路径的每一个位置
    //minPath: 保存最短
    public static void getMinPath(int[][] mat, int row, int col, int x, int y, int[][] book, ArrayList<Node> path,ArrayList<Node> minPath) {
        if(x < 0 || x >= row || y < 0 || y >= col || book[x][y] == 1 || mat[x][y] == 1) {
            return;
        } else {
            path.add(new Node(x,y));
            book[x][y] = 1;
            //判断是否为出口
            if(x == row-1 && y == col-1) {
                //一条新路径产生
                if(minPath.size() == 0 || path.size() < minPath.size()) {
                    minPath.clear();
                    for (Node node:path) {
                        minPath.add(node);
                    }
                }
            }
            getMinPath(mat,row,col,x-1,y,book,path,minPath);
            getMinPath(mat,row,col,x+1,y,book,path,minPath);
            getMinPath(mat,row,col,x,y-1,book,path,minPath);
            getMinPath(mat,row,col,x,y+1,book,path,minPath);
            path.remove(path.size()-1);
            book[x][y] = 0;
        }
    }
}
